# -*- encoding: utf-8 -*-

class QuickSort:
    '''Algoritmo de ordenação por comparação.'''

    def __init__(self, unsortedList, firstIndex, lastIndex):
		'''Construtor da classe
		@param unsortedList -> lista que vai ser ordenada
		@param firstIndex -> index do primeiro elemento da lista que faz parte da ordenação
		@param lastIndex -> index do ultimo elemento da lista que faz parta da ordenação
		'''

		self.unsortedList = unsortedList
		self.firstIndex = firstIndex
		self.lastIndex = lastIndex
		self.sort(unsortedList, firstIndex, lastIndex)


    def sort(self, unsortedList, firstIndex, lastIndex):
		'''Se o firstIndex for menor que o lastIndex,
		chama a função partition() e guarda o valor retornado pela mesma.
		@param unsortedList -> lista que vai ser ordenada
		@param firstIndex -> index do primeiro elemento da lista que faz parte da ordenação
		@param lastIndex -> index do ultimo elemento da lista que faz parta da ordenação
		'''
		if firstIndex < lastIndex:
		    pivot = self.partition(unsortedList, firstIndex, lastIndex)
		    QuickSort(unsortedList, firstIndex, pivot - 1)
		    QuickSort(unsortedList, pivot + 1, lastIndex)
	    

    def partition(self, unsortedList, firstIndex, lastIndex):
		'''Compara todos os valores contidos entre os indexes recebidos com o valor do último index,
		passa todos os que são menores para a esquerda e depois passa o valor do último index para
		o index que divide esses valores dos restantes, passando este index a ser o próximo pivot.
		@param unsortedList -> lista que vai ser ordenada
		@param firstIndex -> index do primeiro elemento da lista que faz parte da ordenação
		@param lastIndex -> index do ultimo elemento da lista que faz parta da ordenação
		@return pivot -> exchanger + 1 
		'''
		self.unsortedList = unsortedList
		self.firstIndex = firstIndex
		self.lastIndex = lastIndex
		
		lastValue = unsortedList[lastIndex]
		exchanger = firstIndex - 1 #Index para trocar o valor com o valor da posição em análise
                                                 #caso esta seja <= que o último valor da lista
		
		for position in range(firstIndex, lastIndex):
			if unsortedList[position] <= lastValue:
				exchanger = exchanger + 1
				unsortedList[exchanger], unsortedList[position] = unsortedList[position], unsortedList[exchanger]
		unsortedList[exchanger + 1], unsortedList[lastIndex] = unsortedList[lastIndex], unsortedList[exchanger + 1]
		return exchanger + 1